{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #K-th Smallest Prime Fraction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: kthSmallestPrimeFraction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #第 K 个最小的素数分数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个按递增顺序排序的数组 <code>arr</code> 和一个整数 <code>k</code> 。数组 <code>arr</code> 由 <code>1</code> 和若干 <strong>素数</strong>&nbsp; 组成，且其中所有整数互不相同。</p>\n",
    "\n",
    "<p>对于每对满足 <code>0 &lt;= i &lt; j &lt; arr.length</code> 的 <code>i</code> 和 <code>j</code> ，可以得到分数 <code>arr[i] / arr[j]</code> 。</p>\n",
    "\n",
    "<p>那么第&nbsp;<code>k</code>&nbsp;个最小的分数是多少呢?&nbsp; 以长度为 <code>2</code> 的整数数组返回你的答案, 这里&nbsp;<code>answer[0] == arr[i]</code>&nbsp;且&nbsp;<code>answer[1] == arr[j]</code> 。</p>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,2,3,5], k = 3\n",
    "<strong>输出：</strong>[2,5]\n",
    "<strong>解释：</strong>已构造好的分数,排序后如下所示: \n",
    "1/5, 1/3, 2/5, 1/2, 3/5, 2/3\n",
    "很明显第三个最小的分数是 2/5\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,7], k = 1\n",
    "<strong>输出：</strong>[1,7]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= arr.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= arr[i] &lt;= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>arr[0] == 1</code></li>\n",
    "\t<li><code>arr[i]</code> 是一个 <strong>素数</strong> ，<code>i &gt; 0</code></li>\n",
    "\t<li><code>arr</code> 中的所有数字 <strong>互不相同</strong> ，且按 <strong>严格递增</strong> 排序</li>\n",
    "\t<li><code>1 &lt;= k &lt;= arr.length * (arr.length - 1) / 2</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你可以设计并实现时间复杂度小于 <code>O(n<sup>2</sup>)</code> 的算法解决此问题吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [k-th-smallest-prime-fraction](https://leetcode.cn/problems/k-th-smallest-prime-fraction/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [k-th-smallest-prime-fraction](https://leetcode.cn/problems/k-th-smallest-prime-fraction/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,5]\\n3', '[1,7]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        n = len(arr)\n",
    "        def check_num(mid):\n",
    "            i = 0\n",
    "            ans = 0\n",
    "            x, y = 0, 1\n",
    "            for j in range(1, n):\n",
    "                while i < n - 1 and arr[i]/arr[j] < mid:\n",
    "                    #print(arr[i], arr[j])\n",
    "                    i = i + 1 \n",
    "                ans = ans + i \n",
    "                #print(ans)\n",
    "                if i - 1 >= 0 and arr[i - 1] / arr[j] > x / y:\n",
    "                    x, y = arr[i - 1], arr[j]\n",
    "                i = 0\n",
    "            return ans, [x, y]\n",
    "        left, right = 0,1\n",
    "        while True:\n",
    "            mid = (left + right) / 2\n",
    "            ans, l = check_num(mid)\n",
    "            if ans == k:\n",
    "                return l\n",
    "            elif ans < k:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        from functools import reduce\n",
    "        from heapq import heappush, heappop\n",
    "        def lcm(x, y):\n",
    "            a, b = x, y\n",
    "            while y:\n",
    "                x, y = y, x % y\n",
    "            return a * b // x\n",
    "\n",
    "        LCM, q, N = reduce(lcm, arr), [], len(arr)\n",
    "\n",
    "        #print(LCM)\n",
    "\n",
    "        for i in range(N - 1):\n",
    "            heappush(q, [arr[i] * LCM // arr[N - 1], i, N - 1])\n",
    "\n",
    "        for _ in range(k - 1):\n",
    "            _, i, j = heappop(q)\n",
    "            if j - 1 > i:\n",
    "                heappush(q, [arr[i] * LCM // arr[j - 1], i, j - 1])\n",
    "\n",
    "        return [arr[q[0][1]], arr[q[0][2]]]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        from functools import reduce\n",
    "        from heapq import heappush, heappop\n",
    "        def lcm(x, y):\n",
    "            a, b = x, y\n",
    "            while y:\n",
    "                x, y = y, x % y\n",
    "            return a * b // x\n",
    "\n",
    "        LCM, q, N = reduce(lcm, arr), [], len(arr)\n",
    "\n",
    "        #print(LCM)\n",
    "        numerators = [arr[i] * LCM for i in range(N)]\n",
    "\n",
    "        for i in range(N - 1):\n",
    "            heappush(q, [numerators[i] // arr[N - 1], i, N - 1])\n",
    "\n",
    "        for _ in range(k - 1):\n",
    "            _, i, j = heappop(q)\n",
    "            if j - 1 > i:\n",
    "                heappush(q, [numerators[i] // arr[j - 1], i, j - 1])\n",
    "\n",
    "        return [arr[q[0][1]], arr[q[0][2]]]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        dp={}\n",
    "        queue = []\n",
    "        for j in range(1, len(arr)):\n",
    "            item = (arr[0]/arr[j], arr[0], arr[j])\n",
    "            heapq.heappush(queue, item)\n",
    "            dp[arr[j]] = [arr[i] for i in range(1, j)]\n",
    "        \n",
    "        for ki in range(k):\n",
    "            v, ni, nj = heapq.heappop(queue)\n",
    "            if ki == k-1:\n",
    "                return [ni, nj]\n",
    "            if len(dp[nj])>0:\n",
    "                ni = dp[nj][0]\n",
    "                item = (ni/nj, ni, nj)\n",
    "                dp[nj] = dp[nj][1:]\n",
    "                heapq.heappush(queue, item)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Frac:\n",
    "    def __init__(self, i, j, x, y):\n",
    "        self.i, self.j, self.x, self.y = i, j, x, y\n",
    "    def __lt__(self, other):\n",
    "        return self.x * other.y < self.y * other.x\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        n = len(arr)\n",
    "        h = [Frac(0, n-1, arr[0], arr[n-1])]\n",
    "        seen = [[0]*n for i in range(n)]\n",
    "        seen[0][n-1] = 1\n",
    "        \n",
    "        while k:\n",
    "            f = heapq.heappop(h)\n",
    "            for i,j in [(f.i+1, f.j), (f.i, f.j-1)]:\n",
    "                if i < j < n and not seen[i][j]:\n",
    "                    seen[i][j] = 1\n",
    "                    heapq.heappush(h, Frac(i, j, arr[i], arr[j]))\n",
    "            k -= 1\n",
    "        return [f.x, f.y]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def kthSmallestPrimeFraction(self, primes, K):\n",
    "        from fractions import Fraction\n",
    "        def under(x):\n",
    "            # Return the number of fractions below x,\n",
    "            # and the largest such fraction\n",
    "            count = best = 0\n",
    "            i = -1\n",
    "            for j in range(1, len(primes)):\n",
    "                while primes[i+1] < primes[j] * x:\n",
    "                    i += 1\n",
    "                count += i+1\n",
    "                if i >= 0:\n",
    "                    best = max(best, Fraction(primes[i], primes[j]))\n",
    "            return count, best\n",
    "\n",
    "        # Binary search for x such that there are K fractions\n",
    "        # below x.\n",
    "        lo, hi = 0.0, 1.0\n",
    "        while hi - lo > 1e-9:\n",
    "            mi = (lo + hi) / 2.0\n",
    "            count, best = under(mi)\n",
    "            if count < K:\n",
    "                lo = mi\n",
    "            elif count > K:\n",
    "                hi = mi\n",
    "            else:\n",
    "                ans = best\n",
    "                return ans.numerator, ans.denominator\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        self.a = arr[0]\n",
    "        self.b = arr[-1]\n",
    "\n",
    "        left, right = 0, 1\n",
    "        while True:\n",
    "            mid = (left + right) / 2.0\n",
    "            count = self.check(mid, arr)\n",
    "            print(mid, count)\n",
    "            if count > k:\n",
    "                right = mid\n",
    "            elif count < k:\n",
    "                left = mid\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return [self.a, self.b]\n",
    "\n",
    "    def check(self, x, arr):\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        large = 0\n",
    "        for j in range(1, len(arr)):\n",
    "            while arr[i+1] * 1.0 / arr[j] <= x:\n",
    "                i += 1\n",
    "            \n",
    "            if arr[i] * 1.0 / arr[j] <= x:\n",
    "                ans += i+1\n",
    "                if arr[i] * 1.0 / arr[j] > large:\n",
    "                    self.a, self.b = arr[i], arr[j]\n",
    "                    large = arr[i] * 1.0 / arr[j]        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        fractions = defaultdict(list)\n",
    "        for i in range(len(arr) - 1):\n",
    "            for j in range(i + 1, len(arr)):\n",
    "                fractions[i].append(j)\n",
    "        heap = []\n",
    "        for i in fractions:\n",
    "\n",
    "            heap.append((arr[i] / arr[j], i, j))\n",
    "\n",
    "        # k = 1\n",
    "        heapq.heapify(heap)\n",
    "\n",
    "        count = 1\n",
    "        while True:\n",
    "            _, i, j = heapq.heappop(heap)\n",
    "            if count == k:\n",
    "                return [arr[i],  arr[j]]\n",
    "            fractions[i].pop()\n",
    "            if len(fractions[i]) > 0:\n",
    "                j = fractions[i][-1]\n",
    "                heapq.heappush(heap, (arr[i] / arr[j], i, j))\n",
    "            count += 1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        stack = []\n",
    "        a, b = 0, 0\n",
    "        l, r, n = 0.0, 1.0, len(arr)\n",
    "        lst = [[] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                lst[i].append(arr[j] / arr[i])\n",
    "        def check(x):\n",
    "            nonlocal a, b, n\n",
    "            res = 0\n",
    "            top = 0\n",
    "            j = 1\n",
    "            while j < n:\n",
    "                # while arr[i+1] / arr[j] <= x:\n",
    "                #     i += 1\n",
    "                idx = bisect_left(lst[j], x, 0, j)\n",
    "                if idx > 0 and lst[j][idx-1] <= x:\n",
    "                    res += idx\n",
    "                    if lst[j][idx-1] > top:\n",
    "                        a, b = arr[idx-1], arr[j]\n",
    "                        top = lst[j][idx-1]\n",
    "                j += 1\n",
    "            return res\n",
    "\n",
    "        while l < r:\n",
    "            mid = (l + r) / 2\n",
    "            num = check(mid)\n",
    "            if num > k: r = mid\n",
    "            elif num < k: l = mid\n",
    "            else: break\n",
    "        return [a, b]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        answer = []\n",
    "        xiaoshu = []\n",
    "        for i in range(len(arr)):\n",
    "            for j in range(i,len(arr)):\n",
    "                xiaoshu.append(arr[i]/arr[j])\n",
    "        xiaoshu.sort()\n",
    "        print(xiaoshu[k-1])\n",
    "        for i in range(len(arr)):\n",
    "            for j in range(i,len(arr)):\n",
    "                if(arr[i]/arr[j]==xiaoshu[k-1]):\n",
    "                    answer.append(arr[i])\n",
    "                    answer.append(arr[j])\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        #m=list(map(lambda x:arr[0]/x,arr[1:]))\n",
    "        #tt=arr[0]/arr[1]\n",
    "        m=[]\n",
    "        n = len(arr)\n",
    "        for i in range(n-1):\n",
    "            m.extend(map(lambda x:arr[i]/x,arr[i+1:]))\n",
    "            #m.extend(z)\n",
    "            #tt=max(tt,z[0])\n",
    "            #if len(m)>k:\n",
    "            #   if arr[i+1]/arr[-1]>tt:\n",
    "            #       return [tt,arr[i+1]/arr[-1],i]\n",
    "            #     break\n",
    "        m.sort()\n",
    "        for i in range(1,n):\n",
    "            t=arr[i]*m[k-1]\n",
    "            #s=round(t)\n",
    "            if abs(round(t)-t)<0.0000001:\n",
    "                #if s in arr:\n",
    "                return[round(t),arr[i]]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        res_lis = []\n",
    "        for i in range(len(arr)-1):\n",
    "            for j in range(i+1, len(arr)):\n",
    "                res = arr[i] / arr[j]\n",
    "                res_lis.append(res)\n",
    "        result = sorted(res_lis, reverse=False)\n",
    "        for i in range(len(arr)-1):\n",
    "            for j in range(i+1, len(arr)):\n",
    "                if result[k-1] == arr[i] / arr[j]:\n",
    "                    return [arr[i], arr[j]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        n = len(arr)\n",
    "        sort = []\n",
    "        labled = [[0]*n for i in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                labled[i][j] = (arr[i]/arr[j])\n",
    "                sort.append(labled[i][j])\n",
    "        sort.sort()\n",
    "        goal = sort[k-1]\n",
    "        for i in range(n):\n",
    "            if labled[i].count(goal):\n",
    "                j = labled[i].index(goal)\n",
    "                return [arr[i],arr[j]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        import queue\n",
    "        n = len(arr)\n",
    "        cur = []\n",
    "        for i in range(n):\n",
    "            q = queue.Queue()\n",
    "            for t in range(n-1, i, -1):\n",
    "                q.put(t)\n",
    "            cur.append(q)\n",
    "\n",
    "        h = []\n",
    "        heapq.heappush(h, [arr[0] / arr[n-1], 0, n-1])\n",
    "        cur[0].get()\n",
    "        ans = [arr[0], arr[n-1]]\n",
    "        while (k > 0):\n",
    "            top = heapq.heappop(h)\n",
    "            i, j = top[1], top[2]\n",
    "            ans = [arr[i], arr[j]]\n",
    "            if not cur[i].empty():\n",
    "                j_ = cur[i].get()\n",
    "                heapq.heappush(h, [arr[i] / arr[j_], i, j_])\n",
    "            if not cur[i+1].empty():\n",
    "                j_ = cur[i+1].get()\n",
    "                heapq.heappush(h, [arr[i+1] / arr[j_], i+1, j_])\n",
    "\n",
    "            k -= 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        if k == 1:\n",
    "            return 1, arr[-1]\n",
    "\n",
    "        N = len(arr)\n",
    "        l = []\n",
    "\n",
    "        if k == N*(N-1)//2:\n",
    "            for i in range(N - 1):\n",
    "                vi, vi1 = arr[i], arr[i + 1]\n",
    "                l.append((vi/vi1, vi, vi1))\n",
    "            l.sort()\n",
    "            return l[-1][1:]\n",
    "\n",
    "        #先从1开始计算到k\n",
    "        num = N - 1\n",
    "        for i in range(N - 1, 0, -1):\n",
    "            vi = arr[i]\n",
    "            l.append((1/vi, 1, vi))\n",
    "\n",
    "        i = 0\n",
    "        if num < k:\n",
    "            for i in range(1, N - 1):\n",
    "                num += N - i - 1\n",
    "                vi = arr[i]\n",
    "                p = 0\n",
    "\n",
    "                for j in range(N - 1, i, -1):\n",
    "                    vj = arr[j]\n",
    "                    f = vi / vj, vi, vj\n",
    "                    p = bisect.bisect_left(l, f, p)\n",
    "                    l.insert(p, f)\n",
    "\n",
    "                if num >= k:\n",
    "                    break\n",
    "\n",
    "        #从最小的开始算\n",
    "        for s in range(N - 2 - i, 0, -1):\n",
    "            minp = num\n",
    "            for j in range(i + 1, N - s):\n",
    "                v1 = arr[j]\n",
    "                v2 = arr[j+s]\n",
    "                f = v1/v2, v1, v2\n",
    "                p = bisect.bisect_left(l, f)\n",
    "                l.insert(p, f)\n",
    "                minp = min(minp, p)\n",
    "\n",
    "            #print(\"***\", i, s, minp)\n",
    "            if minp >= k - 1:\n",
    "                return l[k - 1][1:]\n",
    "\n",
    "        return l[k-1][1:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        import queue\n",
    "        import fractions\n",
    "        n = len(arr)\n",
    "        l = [[] for _ in range(n)]\n",
    "        for i in range(n - 1):\n",
    "            for j in reversed(range(i + 1, n)):\n",
    "                l[i].append((arr[i], arr[j]))\n",
    "        \n",
    "        hq = queue.PriorityQueue()\n",
    "        for i in range(n - 1):\n",
    "            fra = l[i][0]\n",
    "            hq.put((fra[0] / fra[1], fra[0], fra[1], i, 0))\n",
    "        \n",
    "        for i in range(k):\n",
    "            v, a, b, i, j = hq.get()\n",
    "            if j < len(l[i]) - 1:\n",
    "                fra = l[i][j + 1]\n",
    "                hq.put((fra[0] / fra[1], fra[0], fra[1], i, j + 1))\n",
    "\n",
    "        return [a, b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 以分母分组，每组分子递增，转化为从n-1个递增数组中找k大\n",
    "class node:\n",
    "    def __init__(self, i, x):\n",
    "        self.i = i\n",
    "        self.x = x[0]\n",
    "        self.y = x[1]\n",
    "    def __lt__(self, a):\n",
    "        return self.x*a.y < self.y*a.x\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        n = len(arr)\n",
    "        a = [[] for _ in range(n)]\n",
    "        def cmp(a,b):\n",
    "            return a[0]*b[1] - a[1]*b[0]\n",
    "        for i in range(1, n):\n",
    "            for j in range(0,i):\n",
    "                a[i].append((arr[j],arr[i]))\n",
    "\n",
    "        q = []\n",
    "        for i, p in enumerate(a):\n",
    "            if len(p):\n",
    "                heapq.heappush(q, node(i,p.pop(0)))\n",
    "        for _ in range(k-1):\n",
    "            x = heapq.heappop(q)\n",
    "            if len(a[x.i]):\n",
    "                heapq.heappush(q, node(x.i,a[x.i].pop(0)))\n",
    "        return [q[0].x, q[0].y]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        # 大顶堆, 单元为二元组(arr[i], arr[j])\n",
    "        # 时间复杂度为O(klogN)\n",
    "\n",
    "        m = 0\n",
    "        heap = []\n",
    "        lens = len(arr)\n",
    "        for i in range(lens - 1):\n",
    "            for j in range(i + 1, lens):\n",
    "                if m < k:\n",
    "                    heap.append((arr[i], arr[j]))\n",
    "                    m += 1\n",
    "                    if m == k:\n",
    "                        for e in range((len(heap) - 1) // 2, -1, -1):\n",
    "                            self.adjust_heap(heap, e, len(heap))\n",
    "                elif (arr[i] / arr[j]) < (heap[0][0] / heap[0][1]):\n",
    "                    heap[0] = (arr[i], arr[j])\n",
    "                    self.adjust_heap(heap, 0, k)\n",
    "        return [heap[0][0], heap[0][1]]\n",
    "\n",
    "\n",
    "\n",
    "    def adjust_heap(self, heap: List, pos: int, lens: int):\n",
    "        temp = heap[pos]\n",
    "        childpos = pos * 2 + 1\n",
    "        while childpos < lens:\n",
    "            if childpos < lens - 1 and heap[childpos + 1][0] / heap[childpos + 1][1] > heap[childpos][0] / heap[childpos][1]:\n",
    "                childpos += 1\n",
    "            if temp[0] / temp[1] >= heap[childpos][0] / heap[childpos][1]:\n",
    "                break\n",
    "            heap[pos] = heap[childpos]\n",
    "            pos = childpos\n",
    "            childpos = 2 * childpos + 1\n",
    "        heap[pos] = temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def kthSmallestPrimeFraction(self, arr, k):\n",
    "        \"\"\"\n",
    "        :type arr: List[int]\n",
    "        :type k: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "\n",
    "        n = len(arr)\n",
    "        matrix = [[1.0*arr[i]/arr[j] for j in range(n-1,-1,-1)] for i in range(n)] \n",
    "\n",
    "        l = matrix[0][0]\n",
    "        r = 1 \n",
    "        res = [0,0]\n",
    "        while l<r:\n",
    "            mid = (l+r)/2 \n",
    "            r_tmp,c_tmp = n-1,0 \n",
    "            r_max,c_max,val_max = 0,0,-1\n",
    "            r_min,c_min,val_min = 0,0,1e5\n",
    "            num = 0\n",
    "            while r_tmp>=0:\n",
    "                if c_tmp<n and matrix[r_tmp][c_tmp]<=mid:\n",
    "                    c_tmp += 1\n",
    "                else:\n",
    "                    if c_tmp>0 and matrix[r_tmp][c_tmp-1]>val_max:\n",
    "                        r_max,c_max,val_max = r_tmp,c_tmp-1,matrix[r_tmp][c_tmp-1]\n",
    "                    if c_tmp<n and matrix[r_tmp][c_tmp]<val_min:\n",
    "                        r_min,c_min,val_min = r_tmp,c_tmp,matrix[r_tmp][c_tmp] \n",
    "                    num += c_tmp \n",
    "                    r_tmp -= 1 \n",
    "            if num==k:\n",
    "                res = [r_max,c_max]\n",
    "                break\n",
    "            elif num<k:\n",
    "                l = val_min \n",
    "            else:\n",
    "                r = val_max \n",
    "\n",
    "        return [arr[res[0]],arr[n-1-res[1]]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(len(arr)):\n",
    "            for j in range(len(arr)):\n",
    "                res.append(arr[i]/arr[j])\n",
    "        res.sort()\n",
    "        # print(res)\n",
    "        ans = []\n",
    "        for i in range(len(arr)):\n",
    "            for j in range(len(arr)):\n",
    "                if res[k-1] == arr[i]/arr[j]:\n",
    "                    ans.append(arr[i])\n",
    "                    ans.append(arr[j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 初始化 + 后续维护\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr, k: int):\n",
    "        from heapq import heappop, heappush\n",
    "        n = len(arr)\n",
    "        q = [(arr[i]/arr[n-1], i, n-1) for i in range(0, n-1)]\n",
    "        ans = []\n",
    "        while len(q) != 0 and len(ans) < k:\n",
    "            _, i, j = heappop(q)\n",
    "            ans.append([arr[i], arr[j]])\n",
    "            if j - 1 >= 0:\n",
    "                heappush(q, (arr[i]/arr[j-1], i, j-1))\n",
    "        return ans[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        import numpy as np\n",
    "        arr_array = np.array(arr).reshape(1,-1)\n",
    "        big_matrix = np.dot(arr_array.T, 1/arr_array)\n",
    "        big_array = np.unique(big_matrix.reshape(-1))\n",
    "        index = np.where(big_matrix == big_array[k-1])\n",
    "        return [arr[index[0][0]], arr[index[1][0]]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        import heapq\n",
    "        pq = []\n",
    "        res = []\n",
    "        p = 1\n",
    "        for i in range(1, len(arr)):\n",
    "            heapq.heappush(pq, [arr[0]/arr[i], 0, i])\n",
    "        \n",
    "        while p <= k and pq:\n",
    "            num, i, j = heapq.heappop(pq)\n",
    "            p += 1\n",
    "            res.append([arr[i], arr[j]])\n",
    "            if i + 1 < len(arr):\n",
    "                heapq.heappush(pq, [arr[i+1]/arr[j], i+1, j])\n",
    "        return [arr[i], arr[j]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        n = len(arr)\n",
    "        pq = []\n",
    "        res = []\n",
    "        for i in range(n - 1):\n",
    "            heapq.heappush(pq, [arr[0]/arr[n-1 - i], 0, n - 1 - i])\n",
    "        while len(res) < k and pq:\n",
    "            _, a, b = heapq.heappop(pq)\n",
    "            res.append([arr[a], arr[b]])\n",
    "            if a + 1 < n:\n",
    "                heapq.heappush(pq, [arr[a+1]/arr[b], a+1, b])\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        score_lst = []\n",
    "        for i in range(len(arr)-1):\n",
    "            score_lst.append([(arr[i], arr[j]) for j in range(len(arr)-1, i, -1)])\n",
    "        # print(score_lst)  # 升序数组合并\n",
    "        scores = self.merge(score_lst)\n",
    "        return scores[k-1]\n",
    "    \n",
    "    def merge(self, score_lst):\n",
    "        def merge_lst(list1, list2):\n",
    "            tmp = []\n",
    "            i, j = 0, 0\n",
    "            while i < len(list1) and j < len(list2):\n",
    "                if list1[i][0] * list2[j][1] < list2[j][0] * list1[i][1]:\n",
    "                    tmp.append(list1[i])\n",
    "                    i += 1\n",
    "                else:\n",
    "                    tmp.append(list2[j])\n",
    "                    j += 1\n",
    "            if i < len(list1):\n",
    "                tmp.extend(list1[i:])\n",
    "            if j < len(list2):\n",
    "                tmp.extend(list2[j:])\n",
    "            return tmp\n",
    "\n",
    "        while len(score_lst) > 1:\n",
    "            list1 = score_lst.pop()\n",
    "            list2 = score_lst.pop()\n",
    "            res = merge_lst(list1, list2)\n",
    "            score_lst.insert(0, res)\n",
    "        return score_lst[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        n = len(arr)\n",
    "        h = []\n",
    "        heapq.heappush(h, [arr[0] / arr[-1], 0, n - 1])\n",
    "        z = [0] * n\n",
    "        z[-1] = 1\n",
    "        for i in range(k):\n",
    "            p = heapq.heappop(h)\n",
    "            x, y = p[1], p[2]\n",
    "            if z[y] < y:\n",
    "                heapq.heappush(h, [arr[z[y]] / arr[y], z[y], y])\n",
    "                z[y] += 1\n",
    "            if y - 1 > 0 and z[y - 1] < y - 1:\n",
    "                heapq.heappush(h, [arr[z[y - 1]] / arr[y - 1], z[y - 1], y - 1])\n",
    "                z[y - 1] += 1\n",
    "        return [arr[x], arr[y]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        a = len(arr)\n",
    "        fen = []\n",
    "        m = []\n",
    "        n = []\n",
    "        for i in range(a):\n",
    "            for j in range(i+1,a):\n",
    "                fen.append(arr[i]/arr[j])\n",
    "                m.append(i)\n",
    "                n.append(j)\n",
    "        s = sorted(fen)\n",
    "        p = fen.index(s[k-1])\n",
    "        return [arr[m[p]],arr[n[p]]]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr = sorted(arr)\n",
    "        ans = []\n",
    "        for i in range(len(arr) - 1):\n",
    "            for j in range(1, len(arr)):\n",
    "                ans.append(arr[i] / arr[j])\n",
    "        ans = sorted(ans)\n",
    "        res = []\n",
    "        for i in range(len(arr) - 1):\n",
    "            for j in range(1, len(arr)):\n",
    "                if arr[i] / arr[j] == ans[k-1]:\n",
    "                    res = [arr[i], arr[j]]\n",
    "                    return res\n",
    "        return res\n",
    "                    \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(len(arr)):\n",
    "            for j in range(i+1, len(arr)):\n",
    "                res.append((arr[i] / (arr[j] * 1.0), arr[i], arr[j]))\n",
    "        res.sort()\n",
    "        return res[k-1][1:]\n",
    "        # print(res)\n",
    "        # print(res[k-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        heap=[]\n",
    "        n=len(arr)\n",
    "        for i in range(0,n):\n",
    "            for j in range(i+1,n):\n",
    "                heapq.heappush(heap,(arr[i]/arr[j],arr[i],arr[j]))\n",
    "        while k > 1:\n",
    "            heapq.heappop(heap)\n",
    "            k -= 1\n",
    "        _,x,y=heapq.heappop(heap)\n",
    "        return [x,y]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        # 最大堆\n",
    "        n = len(arr)\n",
    "        mheap = []\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                cur = arr[i] / arr[j]\n",
    "                if len(mheap)==k:\n",
    "                    if cur<-mheap[0][0]:\n",
    "                        heapq.heappop(mheap)\n",
    "                        heapq.heappush(mheap, (-cur, arr[i], arr[j]))\n",
    "                else:\n",
    "                    heapq.heappush(mheap, (-cur, arr[i], arr[j]))\n",
    "        return [mheap[0][1], mheap[0][2]]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "\n",
    "        def cmp(l, r, k):\n",
    "            # if l>=r:\n",
    "            #     return\n",
    "            i, j=l, r\n",
    "            while i<j:\n",
    "                while i<j and nums[j][0]*nums[l][1]>=nums[l][0]*nums[j][1]:\n",
    "                    j-=1\n",
    "                while i<j and nums[l][0]*nums[i][1]>=nums[i][0]*nums[l][1]:\n",
    "                    i+=1\n",
    "                nums[i], nums[j]=nums[j], nums[i]\n",
    "            nums[l], nums[i]=nums[i], nums[l]\n",
    "            if i==k-1:\n",
    "                return nums[i]\n",
    "            elif i<k-1:\n",
    "                return cmp(i+1, r, k)\n",
    "            else:\n",
    "                return cmp(l, i-1, k)\n",
    "\n",
    "            # cmp(i+1, r, k)\n",
    "            # cmp(l, i-1, k)\n",
    "\n",
    "        if len(arr)==2:\n",
    "            return arr\n",
    "        nums=[]\n",
    "        for i in range(len(arr)-1):\n",
    "            for j in range(i+1, len(arr)):\n",
    "                nums.append([arr[i], arr[j]])\n",
    "        \n",
    "        return cmp(0, len(nums)-1, k)\n",
    "        # cmp(0, len(nums)-1, k)\n",
    "        # print(nums)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "# class Frac:\n",
    "#     def __init__(self, idx: int, idy: int, x: int, y: int):\n",
    "#         self.idx = idx\n",
    "#         self.idy = idy\n",
    "#         self.x = x\n",
    "#         self.y = y\n",
    "\n",
    "#     def __lt__(self, other) -> bool:\n",
    "#         return self.x * other.y < self.y * other.x\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        n = len(arr)\n",
    "        frac = list()\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                frac.append((arr[i], arr[j]))\n",
    "\n",
    "        # def cmp(x: Tuple[int, int], y: Tuple[int, int]):\n",
    "        #     # cmp_to_key()中 < 对应-1; >对应1; ==对应0\n",
    "        #     return -1 if x[0] * y[1] < y[0] * x[1] else 1\n",
    "\n",
    "        from functools import cmp_to_key\n",
    "        frac.sort(key=lambda x: x[0] / x[1])\n",
    "        return frac[k - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        return sorted(combinations(arr,2),key=lambda x:x[0]/x[1])[k-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        l = len(arr)\n",
    "        res_l = []\n",
    "        for i in range(l-1):\n",
    "            for j in range(i+1,l):\n",
    "                res_l.append((arr[i],arr[j],arr[i]/arr[j]))\n",
    "        res_l.sort(key = lambda x: x[2])\n",
    "        return res_l[k-1][:2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        cb=[ms for ms in combinations(arr,2)]\n",
    "        fs=sorted([ij[0]/ij[1] for ij in cb])[k-1]\n",
    "        for i in cb:\n",
    "            if i[0]/i[1]==fs:\n",
    "                return list(i)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        n = len(arr)\n",
    "        s = list((arr[j], arr[i]) for i in range(1, n) for j in range(i))\n",
    "        s.sort(key=lambda x:x[0]/x[1])\n",
    "        return s[k-1]\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        heap = []\n",
    "        n = len(arr)\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                heappush(heap, (arr[j] / arr[i], j, i))\n",
    "        for i in range(k):\n",
    "            a, b, c = heappop(heap)\n",
    "        return [arr[b], arr[c]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        # ================ #\n",
    "        def cmp(a, b):\n",
    "            return -1 if a[0] * b[1] < a[1] * b[0] else 1\n",
    "        \n",
    "        nums = []\n",
    "        for i in range(len(arr)):\n",
    "            for j in range(i + 1, len(arr)):\n",
    "                nums.append((arr[i], arr[j]))\n",
    "        \n",
    "        nums.sort(key=cmp_to_key(cmp))\n",
    "        return nums[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        def cmp(x, y):\n",
    "            return 1 if x[0] * y[1] > y[0] * x[1] else -1\n",
    "        frac = []\n",
    "        n = len(arr)\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                frac.append((arr[i], arr[j]))\n",
    "        frac.sort(key=cmp_to_key(cmp))\n",
    "        return [frac[k - 1][0], frac[k - 1][1]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        def cmp(x: Tuple[int, int], y: Tuple[int, int]) -> int:\n",
    "            return -1 if x[0] * y[1] < x[1] * y[0] else 1\n",
    "        \n",
    "        n = len(arr)\n",
    "        frac = list()\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                frac.append((arr[i], arr[j]))\n",
    "        \n",
    "        frac.sort(key=cmp_to_key(cmp))\n",
    "        return list(frac[k - 1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        n = len(arr)\n",
    "        h = []\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if len(h) < k:\n",
    "                    heappush(h,(-arr[i]/arr[j],i,j))\n",
    "                else:\n",
    "                    heappushpop(h,(-arr[i]/arr[j],i,j))\n",
    "        # print(h)\n",
    "        return [arr[h[0][1]],arr[h[0][2]]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        pq = []\n",
    "        n = len(arr)\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                heappush(pq, (arr[i] / arr[j], i, j))\n",
    "        while k:\n",
    "            _, i, j = heappop(pq)\n",
    "            k -= 1\n",
    "        return [arr[i], arr[j]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        h = []\n",
    "        n = len(arr)\n",
    "        from sortedcontainers import SortedList\n",
    "        res = SortedList()\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                res.add([arr[i]/arr[j], arr[i], arr[j]])\n",
    "        #         heappush(h, [arr[i]/arr[j], arr[i], arr[j]])\n",
    "        # print(h)\n",
    "        # print(res)\n",
    "        return res[k-1][1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        n=len(arr)\n",
    "        data=[[arr[i]/arr[j],arr[i],arr[j]] for i in range(n) for j in range(i+1,n)]\n",
    "        data.sort()\n",
    "        data=data[:k]\n",
    "        return [data[-1][1],data[-1][2]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        n = len(arr)\n",
    "        data = []\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                data.append((i, j, arr[i] / arr[j]))\n",
    "        data.sort(key=lambda x: x[2])\n",
    "        return [arr[data[k - 1][0]], arr[data[k - 1][1]]]\n",
    "        # return data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        # begin = 0\n",
    "        # end = len(arr) - 1\n",
    "        # value1_index = answer.copy()\n",
    "        # value2_index = answer.copy()\n",
    "        # answer = []\n",
    "        # while k>0:\n",
    "        #     value1 = arr[value1_index[0]]/arr[value1_index[1]] if(value1_index[1]>value1_index[0]) else 1\n",
    "        #     value2 = arr[value2_index[0]]/arr[value2_index[1]] if(value2_index[1]>value2_index[0]) else 1\n",
    "        #     print(\"For k = {}, value1 = {}/{}, value2 = {}/{}\".format(k, arr[value1_index[0]], arr[value1_index[1]], arr[value2_index[0]], arr[value2_index[1]]))\n",
    "        #     if(value1 < value2):\n",
    "        #         answer = value1_index.copy()\n",
    "        #         if(arr[value1_index[0]+1]/arr[value1_index[1]]<arr[value1_index[0]]/arr[value1_index[1]-1]):\n",
    "        #             value1_index[0] = value1_index[0] + 1\n",
    "        #         else:\n",
    "        #             value1_index[1] = value1_index[1] - 1\n",
    "        #     else:\n",
    "        #         answer = value2_index.copy()\n",
    "        #         if(arr[value2_index[0]+1]/arr[value2_index[1]]<arr[value2_index[0]]/arr[value2_index[1]-1]):\n",
    "        #             value2_index[0] = value2_index[0] + 1\n",
    "        #         else:\n",
    "        #             value2_index[1] = value2_index[1] - 1\n",
    "        #     k = k - 1\n",
    "        # return [arr[answer[0]],arr[answer[1]]]\n",
    "        import numpy as np\n",
    "        arr= np.array(arr)\n",
    "        final = []\n",
    "        for value in arr:\n",
    "            final = final + list(value/arr)\n",
    "        final_copy = final.copy()\n",
    "        final_copy.sort()\n",
    "        result_index = final.index(final_copy[k-1])\n",
    "        x = result_index//len(arr)\n",
    "        y = result_index%len(arr)\n",
    "        return [int(arr[x]),int(arr[y])]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        a = []\n",
    "        for i in range(len(arr)):\n",
    "            for j in range(i+1, len(arr)):\n",
    "                a.append([arr[i], arr[j], arr[i]/arr[j]])\n",
    "        a.sort(key=lambda x:x[2])\n",
    "        return a[k-1][0:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        n = len(arr)\n",
    "        heap = [(arr[0] / arr[n - 1], (0, n - 1))]; used = set()\n",
    "        ans = [arr[0], arr[n - 1]]\n",
    "        if k == 1: return ans\n",
    "        for _ in range(k - 1):\n",
    "            i, j = heappop(heap)[1]\n",
    "            if i + 1 < j and (i + 1, j) not in used:\n",
    "                heappush(heap, (arr[i + 1] / arr[j], (i + 1, j)))\n",
    "                used.add((i + 1, j))\n",
    "            if j - 1 > i and (i, j - 1) not in used:\n",
    "                heappush(heap, (arr[i] / arr[j - 1], (i, j - 1)))\n",
    "                used.add((i, j - 1))\n",
    "            i, j = heap[0][1]\n",
    "            ans = [arr[i], arr[j]]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        n=len(arr)\n",
    "        lst=[]\n",
    "        for j in range(1,n):\n",
    "            for i in range(j):\n",
    "                lst.append([arr[i],arr[j],arr[i]/arr[j]])\n",
    "        lst.sort(key=lambda x:x[2])\n",
    "        return lst[k-1][:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        if not arr:\n",
    "            return []\n",
    "\n",
    "        n = len(arr)\n",
    "        s = [(arr[0]/arr[n-1], 0, n-1)]\n",
    "        visited = {(0, n-1)}\n",
    "        for _ in range(k):\n",
    "            num, i, j = heapq.heappop(s)\n",
    "            \n",
    "            if k == 1:\n",
    "                return [arr[i], arr[j]]\n",
    "            k -= 1\n",
    "            if i + 1 < n and (i+1, j) not in visited:\n",
    "                heapq.heappush(s, (arr[i+1]/arr[j], i+1, j))\n",
    "                visited.add((i + 1, j))\n",
    "            if j - 1 >= 0 and (i, j - 1) not in visited:\n",
    "                heapq.heappush(s, (arr[i]/arr[j - 1], i, j-1))\n",
    "                visited.add((i, j - 1))\n",
    "\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        l = []\n",
    "        for i in range(len(arr)):\n",
    "            for j in range(i, len(arr)):\n",
    "                l.append([arr[i], arr[j], arr[i]/arr[j]])\n",
    "        return sorted(l, key=lambda x: x[2])[k-1][:2]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        l = []\n",
    "        n = len(arr)\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                heapq.heappush(l, (arr[i] / arr[j], arr[i], arr[j]))\n",
    "\n",
    "        return heapq.nsmallest(k, l)[k - 1][1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cmp_to_key\n",
    "\n",
    "\n",
    "def cmp(a, b):\n",
    "    return a[0] * b[1] - a[1] * b[0]\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        res = [[0] * 2 for i in range((len(arr) - 1) * len(arr) // 2)]\n",
    "        index = 0\n",
    "        for i in range(1, len(arr)):\n",
    "            for j in range(i):\n",
    "                res[index][0] = arr[j]\n",
    "                res[index][1] = arr[i]\n",
    "                index += 1\n",
    "        \n",
    "        res = sorted(res, key=cmp_to_key(cmp))\n",
    "        # print(res)\n",
    "        return res[k - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        frcs=[]\n",
    "        l=len(arr)\n",
    "        for i in range(l-1):\n",
    "            for j in range(max(i+1,l-1-k//(i+1)),l):\n",
    "                frcs.append([arr[i]/arr[j],i*l+j])\n",
    "        frcs.sort(key=lambda x:x[0])\n",
    "        return [arr[frcs[k-1][1]//l],arr[frcs[k-1][1]%l]]\n",
    "        '''\n",
    "        l=len(arr)\n",
    "        d=collections.defaultdict(list)\n",
    "        d[arr[0]/arr[l-1]]=[0,l-1]\n",
    "        cnt=0\n",
    "        while cnt<k:\n",
    "            minKey=min(d.keys())\n",
    "            row,col=d.pop(minKey)\n",
    "            cnt+=1\n",
    "            if col>0:\n",
    "                d[arr[row]/arr[col-1]]=[row,col-1]\n",
    "            if row<l-1:\n",
    "                d[arr[row+1]/arr[col]]=[row+1,col]        \n",
    "        return [arr[row],arr[col]]\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        ans = []\n",
    "        for i in range(len(arr)-1):\n",
    "            for j in range(i,len(arr)):\n",
    "                ans.append([arr[i]/arr[j],i,j])\n",
    "        ans.sort()\n",
    "        return [arr[ans[k-1][1]],arr[ans[k-1][2]]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        n = len(arr)\n",
    "        h = []\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if len(h) < k:\n",
    "                    heapq.heappush(h, [-arr[i] / arr[j], i, j])\n",
    "                else:\n",
    "                    if (-arr[i] / arr[j] > h[0][0]):\n",
    "                        heapq.heappop(h)\n",
    "                        heapq.heappush(h, [-arr[i] / arr[j], i, j])\n",
    "\n",
    "        \n",
    "        i, j = h[0][1], h[0][2]\n",
    "        return [arr[i], arr[j]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        h=[]\n",
    "        n=len(arr)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                heapq.heappush(h,(arr[i]/arr[j],(arr[i],arr[j])))\n",
    "        for _ in range(k-1):\n",
    "            heapq.heappop(h)\n",
    "        return list(heapq.heappop(h)[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import  heapq\n",
    "class Node:\n",
    "  def __init__(self, value,arr):\n",
    "    self.value = value\n",
    "    self.arr=arr\n",
    "\n",
    "  def __lt__(self, other):\n",
    "    return self.arr[self.value[0]]*self.arr[other.value[1]] <self.arr[self.value[1]]*self.arr[other.value[0]] \n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        if k==1:\n",
    "            return [arr[0],arr[-1]]\n",
    "        candidate=[Node([0,len(arr)-1],arr)]\n",
    "        flag={}\n",
    "        flag[(0,len(arr)-1)]=True\n",
    "        while k>0:\n",
    "            k-=1\n",
    "            t=heapq.heappop(candidate)\n",
    "            #print([arr[t.value[0]],arr[t.value[1]]])\n",
    "            if t.value[1]-t.value[0]>1:\n",
    "                t1=Node([t.value[0]+1,t.value[1]],arr)\n",
    "                t2=Node([t.value[0],t.value[1]-1],arr)\n",
    "                if (t.value[0]+1,t.value[1]) not in flag:\n",
    "                  flag[(t.value[0]+1,t.value[1])]=True\n",
    "                  heapq.heappush(candidate,t1)\n",
    "                if (t.value[0],t.value[1]-1) not in flag:\n",
    "                  flag[(t.value[0],t.value[1]-1)]=True\n",
    "                  heapq.heappush(candidate,t2)\n",
    "        return [arr[t.value[0]],arr[t.value[1]]]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "\n",
    "        pq = []\n",
    "        n = len(arr)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                pq.append([arr[i]/arr[j], i, j])\n",
    "        pq.sort(key=lambda x:x[0])\n",
    "        cur = pq[k-1]\n",
    "        return [arr[cur[1]], arr[cur[2]]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        \n",
    "        hash=dict()\n",
    "        for i in range(len(arr)-1):\n",
    "            for j in range(i,len(arr)):\n",
    "                hash[str(arr[i])+','+str(arr[j])]=arr[i]/arr[j]\n",
    "        hash_sort=sorted(hash, key=hash.get)\n",
    "        res=str(hash_sort[k-1])\n",
    "        res=res.split(',')\n",
    "        res1=[]\n",
    "        for ele in res:\n",
    "            res1.append(int(ele))\n",
    "        return res1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        import numpy as np\n",
    "        def takeSecond(elem):\n",
    "            return elem[2]\n",
    "        arrAll = []\n",
    "        iCount = 1\n",
    "        for i in arr:\n",
    "            for j in arr[iCount::]:\n",
    "                arrAll.append([i,j,i/j])\n",
    "            iCount = iCount + 1\n",
    "        arrAll.sort(key=takeSecond)\n",
    "        return arrAll[k-1][0:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        sl = SortedList()\n",
    "        for i in range(len(arr)-1):\n",
    "            for j in range(i+1,len(arr)):\n",
    "                sl.add((arr[i]/arr[j],[arr[i],arr[j]]))\n",
    "        # print(sl)\n",
    "        return sl[k-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:\n",
    "        pq = []\n",
    "        n = len(arr)\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1,n):\n",
    "                heappush(pq,(-arr[i]/arr[j],[arr[i],arr[j]]))\n",
    "                if len(pq) > k:\n",
    "                    heappop(pq)\n",
    "        return heappop(pq)[1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
